\subsection{Übungsblatt 5 - Faktorisieren mit quadratischem Sieb}
\subsubsection{Übung (i)}
\paragraph{Aufgabe:}
Sei $n$ eine ungerade zusammengesetzte Zahl.
Zeigen Sie, dass sich mit folgendem Ansatz ein echter Faktor (d.h.\ ungleich $1$ und $n$) finden lässt: 

{\ttfamily
$x$ = $\lceil \sqrt{n} \rceil$

$r$ = $x^2 - n$

falls $r$ keine Quadratzahl ist:

~~$x$ ++
  
~~$r$ = $x^2 - n$

sonst

~~$y$ = $\sqrt{r} \in \Z$

~~Ausgabe der Faktorisierung  
}

Wie lautet die gefundene Faktorisierung? Funktioniert dieses Verfahren immer? Falls ja: wie viele Schritte benötigt es höchstens? Geben Sie ein Beispiel an, bei dem der worst-case vorliegt. Falls nein: Geben Sie ein Beispiel an, bei dem das Verfahren versagt. Gibt es einen Zeitpunkt, bei dem man weiß, dass man abbrechen kann?

\paragraph{Lösung:}

Wenn ein x und ein y gefunden wird, dann sind es auch nicht triviale Teiler:\\
$r= x^2-n=y^2 \Rightarrow n=x^2-y^2=(x+y)(x-y)$ mit $x > y$ und $x, y \in \mathds{N} $\\
Das Verfahren funktioniert immer, unter der Voraussetzung, dass n ungerade ist, d.h. nämlich das die Faktoren ungerade sind und es somit $f_1$  und $f_2$ mit $n=f_1 \cdot f_2$ und $f_1=(x+y)$ und $f_2=(x-y) \Rightarrow x=f_1-y$ und $f_2=f_1-y-y=f_1-2y \Rightarrow$ beide Faktoren müssen entweder gerade sein oder beide Faktoren müssen ungerade sein.

Der Algorithmus sucht den größten Teiler von n, der kleiner als $\sqrt{n}$ ist. Deshalb benötigt er am längsten, wenn der Primfaktor kleiner $\sqrt{n}$ den kleinstmöglichen Wert hat, also 3 (= kleinste, ungerade Primzahl).

Er benötigt dann $\lceil\frac{(n+9)}6 \rceil - \lceil\sqrt{n}\rceil+1$ Schritte, z.B.  bei $n=93=3*31$\\
$s= \lceil\frac{102}6\rceil-\lceil\sqrt{93}\rceil+1=17-10+1=8$\\
d.h. der Algorithmus benötigt 8 Schritte. Im 8. Schritt ist 
$x = 17 \Rightarrow y = (17^2 - 93) = 14$.\\
Also ist der Algorithmus durchgelaufen.
\newpage

\subsubsection{Übung (ii)}
\paragraph{Aufgabe:}
Verwenden Sie das QS mit $B = 5$, um die Zahl $91$ zu faktorisieren.

\paragraph{Lösung:}
Faktorisierung von $n = 91$:

$m = \sqrt{n} = \sqrt{91} = 9$

$B = 5, C = 2$

$F(0)	= (0 + 9)^2 - 91	= -10 	= -1 \cdot 2 \cdot 5$\\
$F(-1)	= (-1 + 9)^2 - 91	= -27 	= -1 \cdot 3^3$\\
$F(2)	= (2 + 9)^2 - 91	= 30 	= 2 \cdot 3 \cdot 5$

$(9 \cdot 8 \cdot 11)^2 = (-1 \cdot 2 \cdot 3^2 \cdot 5)^2 \mod 91$

$\Rightarrow x = 9 \cdot 8 \cdot 11 \equiv 64 \mod 91$ und $y = -1 \cdot 2 \cdot 3^2 \cdot 5  \equiv 1 \mod 91$\\
$\Rightarrow x - y = 64 - 1 = 63$\\
$gcd(91, 63) = 7$

\begin{tabular}{|l|l|l|l|l|} \hline
91 & 63 & 28 & 7 & 1\\\hline
   & 1  &  2 & 4 &	\\\hline
\end{tabular}

$91 = 7 \cdot 13$

\subsubsection{Übung (iii)}
\paragraph{Aufgabe:}
Verwenden Sie das QS, um die Zahl $319$ zu faktorisieren. Welches $B$ haben Sie gewählt?

\paragraph{Lösung:}

Faktorisierung von $n = 319$:

$m = \sqrt{n} = \sqrt{319} = 17$

$B = 5, C = 4$

$F(0) = (0 + 17)^2 - 319 = -30 = -1 \cdot 2 \cdot 3 \cdot 5$\\
$F(1) = (1 + 17)^2 - 319 = 5$\\
$F(-4) = (-4 + 17)^2 - 319 = -150 = -1 \cdot 2 \cdot 3 \cdot 5^2$\\

$(17 \cdot 18 \cdot 13)^2 \equiv (-1 \cdot 2 \cdot 3 \cdot 5^2)^2 \mod 319$

$\Rightarrow X = 17 \cdot 18 \cdot 13 \cdot 20 \equiv 150 \mod 319$ und $y = -1 \cdot 2 \cdot 3 \cdot 5^2 \equiv 169 \mod 319$\\

$x = -y \Rightarrow$ weiter suchen:
 
$F(3) = (3 + 17)^2 - 319 = 81 = 3^4$
 
$(17 \cdot 18 \cdot 13 \cdot 20)^2 \equiv (-1 \cdot 2 \cdot 3^3 \cdot 5^2)^2 \mod 319$

$\Rightarrow x = 17 \cdot 18 \cdot 13 \cdot 20 \equiv 129 \mod 319$ und $y = -1 \cdot 2 \cdot 3^3 * 5^2 \equiv -74 \mod 319$\\
$\Rightarrow x - y = 129 + 74 = 203$

$gcd(319, 203) = 29$

\begin{tabular}{|l|l|l|l|l|l|} \hline
319 & 203 & 116 & 87 & 29 & 1 \\\hline
    &   1 &   1 &  1 &  3 &	  \\\hline
\end{tabular}

$\Rightarrow 319 = 29 \cdot 11$
